A cryptographic system is a computer system that uses cryptography, typically to secure or authenticate data communication between a pair of computing devices connected to one another through a data communication link in the system. Each computing device has a cryptographic unit with the processing capacity to implement one or more cryptographic protocols used to secure or authenticate the data communication. The cryptographic protocols typically perform arithmetic operations on the bit strings representing parameters, messages, or data in the protocols to produce a bit string representing the output from the protocol.
Cryptographic systems can be broadly divided into two categories: systems that employ symmetric-key schemes, and systems that employ asymmetric or public key schemes. In symmetric-key schemes, the correspondents first agree upon a key that is both secret and authentic. Each correspondent then uses this shared secret key to perform operations such as encryption, decryption, and/or data integrity and data origin authentication.
Symmetric-key schemes have relatively high efficiency; however, they suffer from the key distribution problem, that is, the problem of securely distributing the secret key to each entity. A further drawback of symmetric-key schemes is that such schemes generally cannot use digital signatures to provide non-repudiation services. Since the symmetric key is shared among two or more correspondents, when one correspondent uses the key to sign a message, the signature will not be unique because another correspondent possessing the shared secret key could also generate the same signature. In a symmetric-key scheme, with at least two correspondents, A and B, correspondent B would never be able to prove that correspondent A signed a message, and not he. Accordingly, a third party C could not be convinced that B did not sign the message, especially if it was in any way in B's interest to have done so. This is because B shares the symmetric key with A, and therefore B can do anything with the key that A can do. In particular, A can repudiate such signatures, with the claim that B signed, and B would not be able to refute A's assertion.
Public key schemes, on the other hand, eliminate the above-described problem by allowing the use of elegant digital signature schemes that provide non-repudiation services. Public key schemes also eliminate the key distribution problem. In a public key scheme, each correspondent utilizes a private key and a public key related to the private key by a mathematical function. The mathematical function presents a “difficult” mathematical problem to ensure that a private key of a correspondent cannot be obtained from the corresponding public key. An example of one such problem is the discrete logarithm problem over a finite field, which is used as the basis for public key systems that can implement signature algorithms such as the digital signature algorithm (DSA) and key agreement schemes such as the Diffie-Hellman scheme or the Menezes-Qu-Vanstone (MQV) scheme. A particularly robust and efficient system makes use of points on an elliptic curve defined over a finite field. Such systems, referred to as elliptic curve cryptographic (ECC) systems, offer high levels of security at faster computation time than other systems.
The reason public key schemes allow for elegant digital signature algorithms that provide non-repudiation services is because each correspondent has a unique private key that only he knows, and therefore each correspondent can use his private key to generate a unique signature that binds himself to a message. A third party can then use the correspondent's corresponding public key to verify that the signed message did indeed originate from that correspondent. An example of such a signature scheme used in an elliptic curve cryptographic system is referred to as the Elliptic Curve Digital Signature Algorithm (ECDSA).
Public key schemes also avoid the key distribution problem because secret keys are not shared between correspondents and so no distribution of shared secret keys is necessary.
Therefore, public key schemes are advantageous because of the above-discussed properties. However, the drawback of public key schemes is that they are generally not as efficient at performing encryption or decryption operations, or at performing some data integrity operations. Therefore, many current cryptographic systems combine and exploit the strengths of both symmetric key schemes and public key schemes. An example of such a system is one that utilizes key agreement. Correspondent A possesses long-term or static private/public key pair (a, QA) and correspondent B possesses static private/public key pair (b, QB). These static private and public keys are then used in generating a shared symmetric key k to use for each communication session. A and B each calculate the shared key k based on public static and public ephemeral keys it receives from the other party, as well as based on private static and private ephemeral keys it generates itself.
Key agreement schemes are well known in the art. An example of a well-known key agreement scheme is the Menezes-Qu-Vanstone (MQV) scheme, which adapted for an elliptic curve cryptographic systems is known as Elliptic Curve Menezes-Qu-Vanstone (ECMQV) key agreement. Key agreement schemes such as ECMQV are a useful way of distributing (i.e. sharing) secret keys.
In some situations, key agreement participants may require non-repudiation services or vice versa. However, the number of operations required to perform both key agreement and digital signatures can prove to be costly in certain computationally constrained environments. Also, transmitting a signature across a communication channel requires bandwidth, as the signature components must be transmitted to the recipient to allow for verification.